package leetcode.weekly.week322;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

//Solution4Test
public class Solution4 {
	int[] p;

	public void init(int size) {
		p = new int[size];
		for (int i = 0; i < p.length; i++) {
			p[i] = i;
		}
	}

	public void union(int a, int b) {
		p[find(a)] = find(b);
	}

	public int find(int id) {
		if (p[id] != id) {
			p[id] = this.find(p[id]);
		}
		return p[id];
	}

	public boolean isSameSet(int a, int b) {
		return find(a) == find(b);
	}

	public int magnificentSets(int n, int[][] edges) {
		int size = n + 1;
		List<Integer>[] nexts = new ArrayList[size];
		for (int i = 0; i < size; i++) {
			nexts[i] = new ArrayList<>();
		}
		init(size);
		for (int i = 0; i < edges.length; i++) {
			int[] r = edges[i];
			int a = r[0], b = r[1];
			nexts[a].add(b);
			nexts[b].add(a);
			union(a, b);
		}
		Map<Integer, Integer> umap = new HashMap<>();
		for (int i = 1; i <= n; i++) {
			int deep = d(i, nexts);
			if (deep == -1) {
				return -1;
			}
			umap.put(find(i), Math.max(umap.getOrDefault(find(i), 0), deep));
		}
		int ans = 0;
		for (Integer value : umap.values()) {
			ans += value;
		}
		return ans;
	}

	private int d(int start, List<Integer>[] nexts) {
		int ans = 0;
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);
		Map<Integer, Integer> ids = new HashMap<>();
		int id = 1;
		ids.put(start, id);
		while (!queue.isEmpty()) {
			int size = queue.size();
			ans++;
			id++;
			while (size > 0) {
				int cur = queue.poll();
				size--;
				List<Integer> next = nexts[cur];
				for (int n : next) {
					if (ids.containsKey(n)) {
						// cur 从id - 2来，id同层指向同一个n，如果两个都不是，跨层了
						if (ids.get(n) == id - 2 || ids.get(n) == id) {
							continue;
						} else {
							return -1;
						}
					}
					ids.put(n, id);
					queue.add(n);
				}
			}
		}
		return ans;
	}
}
